package com.kevinkk.graph;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
 * 值 0 代表空单元格；
 * 值 1 代表新鲜橘子；
 * 值 2 代表腐烂的橘子。
 * 每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
 * 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
 */

/**
 * 有点类似层序遍历，用一个队列记录下所有的腐烂橘子
 * 每一分钟，取出队列里的全部橘子，然后依次尝试腐败周围的新鲜橘子
 */

public class RottingOranges {
    class Solution {
        public int orangesRotting(int[][] grid) {
            Deque<int[]> que = new ArrayDeque<>();
            int newOrange = 0, res = 0;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == 1) newOrange++;
                    if (grid[i][j] == 2) que.addLast(new int[]{i, j});
                }
            }

            while (!que.isEmpty() && newOrange > 0) {   // 循环判断条件newOrange 必须大于 0，否则会额外多出一轮
                int size = que.size();
                res++;

                for (int k = 0; k < size; k++) {
                    int[] pos = que.removeFirst();
                    int i = pos[0], j = pos[1];
                    // 依次向周围腐蚀
                    if (i > 0 && grid[i - 1][j] == 1) {
                        grid[i - 1][j] = 2;                 // 腐蚀之后需要改变状态
                        newOrange--;                        // 新鲜橘子数量减少
                        que.addLast(new int[]{i - 1, j});   // 腐蚀之后的橘子加入队列
                    }
                    if (i < grid.length - 1 && grid[i + 1][j] == 1) {
                        grid[i + 1][j] = 2;
                        newOrange--;
                        que.addLast(new int[]{i + 1, j});
                    }
                    if (j > 0 && grid[i][j - 1] == 1) {
                        grid[i][j - 1] = 2;
                        newOrange--;
                        que.addLast(new int[]{i, j - 1});
                    }
                    if (j < grid[0].length - 1 && grid[i][j + 1] == 1) {
                        grid[i][j + 1] = 2;
                        newOrange--;
                        que.addLast(new int[]{i, j + 1});
                    }
                }
            }

            return newOrange == 0 ? res : -1;
        }
    }


}
